#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Test2{
public:
	vector<int> preorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> result;
		if(root == NULL){
			return result;
		}
		st.push(root);
		while(!st.empty()){
			TreeNode* cur  = st.top();
			st.pop();
			result.push_back(cur->val);
			if(cur->right){
				st.push(cur->right);
			}
			if(cur->left){
				st.push(cur->left);
			}
		}
		return result;
	}
	vector<int> postOrderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> result;
		if(root == NULL){
			return result;
		}
		st.push(root);
		while(!st.empty()){
			TreeNode* cur  = st.top();
			st.pop();
			result.push_back(cur->val);
			if(cur->left){
				st.push(cur->left);
			}
			if(cur->right){
				st.push(cur->right);
			}
		}
		reverse(result.begin(),result.end());
		return result;
	}
	vector<int> inorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> result;
		TreeNode* cur = root;
		while(cur != NULL || !st.empty()){
			if(cur != NULL){
				st.push(cur);
				cur = cur->left;
			}else{
				cur = st.top();
				st.pop();
				result.push_back(cur->val);
				cur = cur->right;
			}
		}
		return result;
	}
};
class Test{
public:
	vector<int> preorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> result;
		if(root == NULL){
			return result;
		}
		st.push(root);
		while(!st.empty()){
			TreeNode* cur = st.top(); st.pop();
			result.push_back(cur->val);
			if(cur->right){
				st.push(cur->right);
			}
			if(cur->left){
				st.push(cur->left);
			}
		}
		return result;
	}
	vector<int> postorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> result;
		if(root == NULL){
			return result;
		}
		st.push(root);
		while(!st.empty()){
			TreeNode* cur = st.top();st.pop();
			result.push_back(cur->val);
			if(cur->left){
				st.push(cur->left);
			}
			if(cur->right){
				st.push(cur->right);
			}
		}
		int l = 0;
		int r = result.size() - 1;
		while(l<r){
			swap(result[l],result[r]);
			l++;
			r--;
		}
		
		return result;
	}
	vector<int> inorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> result;
		TreeNode* cur = root;
		while(cur != NULL || !st.empty()){
			if(cur != NULL){
				st.push(cur);
				cur = cur ->left;
			}else{
				cur = st.top();st.pop();
				result.push_back(cur->val);
				cur = cur ->right;
			}
		}
		return result;
	}
};


int main(){
	
	
	return 0;
}
